mat = [
    [0, -2, -7, 0],
    [9, 2, -6, 2],
    [-4, 1, -4, 1],
    [-1, 8, 0, -2]
]

def FindMaxInArray(arr):
    maxIdx = 0, 0   # 起点,终点
    maxValue = arr[0]
    for i in range(0, 4):
        for j in range(i, 4):
            tot = 0
            for k in range(i, j + 1):
                tot += arr[k]
            if tot > maxValue:
                maxValue = tot
                maxIdx = i, j
    
    return maxValue, maxIdx

def CombineToArray(mat, beg, end):
    arr = mat[beg][:]
    for i in range(beg + 1, end + 1):
        for j in range(0, 4):
            arr[j] += mat[i][j]

    return arr

def Solve(mat):
    inited = False
    maxValue = 0
    maxIdx = (0, 0), (0, 0) # 起始行列，结束行列
    for i in range(0, 4):
        for j in range(i, 4):
            arr = CombineToArray(mat, i, j)
            val, idx = FindMaxInArray(arr)
            if inited == False:
                maxValue = val
                maxIdx = (i, idx[0]), (j, idx[1])
                inited = True
            else:
                if val > maxValue:
                    maxValue = val
                    maxIdx =  (i, idx[0]), (j, idx[1])

    return maxValue, maxIdx

print(Solve(mat))

# print(CombineToArray(mat, 0, 2))
# print(FindMaxInArray(mat[2]))